#include <vector>
#include <iostream>
using namespace std;

template <class K, class V>
struct HashNode{
  pair<K,V> _kv;
  HashNode<K,V> *_next;
  
public:
  HashNode(const pair<K,V>& kv)
    :_kv(kv),
    _next(nullptr)
  {}
};

template <class K>
struct HashKey{
  size_t operator()(const K& key){
    return (size_t)key;
  }
};

template <>
struct HashKey<string>{
  size_t operator()(const string& str){
    size_t key = 0;
    for(char e : str)
    {
      key *= 131;
      key += e;
    }
    return key;
  }
};

template <class K, class V, class Hash = HashKey<K>>
class HashTable{
  typedef HashNode<K,V> Node;
  vector<Node*> _table;
  size_t _size = 0;

public:
  ~HashTable(){
    for(int i=0; i<_table.size(); ++i)
    {
      Node *cur = _table[i];
      while(cur != nullptr)
      {
        Node *next = cur->_next;
        delete cur;
        cur = next;
      }
      _table[i] = nullptr;
    }
  }
  
  inline unsigned long __stl_next_prime(size_t n)
  {
    static const int __stl_num_primes = 30;
    static const size_t __stl_prime_list[__stl_num_primes] =
    {
      11,  23 ,  53,         97,         193,       389,       769,
      1543,       3079,       6151,      12289,     24593,
      49157,      98317,      196613,    393241,    786433,
      1572869,    3145739,    6291469,   12582917,  25165843,
      50331653,   100663319,  201326611, 402653189, 805306457, 
      1610612741, 3221225473, 4294967291
    };
    
    for(int i = 0; i<__stl_num_primes; ++i)
    {
      if(__stl_prime_list[i] > n)
      {
        return __stl_prime_list[i];
      }
    }
    return -1;
  }

  bool insert(const pair<K,V>& kv){
    //去重
    if(find(kv.first) != nullptr)
    {
      return false;
    }
    Hash hash;
    //载荷因子到1就扩容
    if(_size == _table.size())
    {
      vector<Node*> newtable;
      newtable.resize(__stl_next_prime(_table.size()), nullptr);
      for(int i = 0; i<_table.size(); ++i)
      {
        Node *cur = _table[i];
        while(cur != nullptr)
        {
          size_t hashi = hash(cur->_kv.first) % newtable.size();
          Node *next = cur->_next;
          cur->_next = newtable[hashi];
          newtable[hashi] = cur;
          cur = next;
        }
        _table[i] = nullptr;
      }
      swap(_table, newtable);
    }
    //插入
    size_t hashi = hash(kv.first) % _table.size();
    Node *newnode = new Node(kv);
    newnode->_next = _table[hashi]; 
    _table[hashi] = newnode;
    ++_size;
    return true;
  }

  Node* find(const K& key){
    if(_table.size() == 0)
      return nullptr;
    Hash hash;
    size_t hashi = hash(key) % _table.size();
    Node *cur = _table[hashi];
    while(cur != nullptr)
    {
      if(cur->_kv.first  == key)
      {
        return cur;
      }
      cur = cur->_next;
    }
    return nullptr;
  }

  bool erase(const K& key){
    if(_table.size() == 0)
      return false;
    Hash hash;
    size_t hashi = hash(key) % _table.size();
    Node *prev = nullptr;
    Node *cur = _table[hashi];
    while(cur != nullptr)
    {
      if(cur->_kv.first == key)
      {
        if(_table[hashi] == cur)
          _table[hashi] = cur->_next; 
        else
          prev->_next = cur->_next;
        delete cur;
        --_size;
        return true;
      }
      prev = cur;
      cur = cur->_next;
    }
    return false;
  }

  void printHT(){
    for(int i=0; i<_table.size(); ++i)
    {
      Node *cur = _table[i];
      while(cur != nullptr)
      {
        cout << cur->_kv.first << ":" << cur->_kv.second << endl;
        cur = cur->_next;
      }
    }
  }

  size_t bucket_count(){
    size_t cnt = 0;
    for(int i=0; i<_table.size(); ++i)
    {
      if(_table[i] != nullptr)
        ++cnt;
    }
    return cnt;
  }

  size_t size(){
    return _size;
  }

  size_t table_size(){
    return _table.size();
  }

  size_t max_bucket_len(){
    size_t max_len = 0;
    for(int i=0; i<_table.size(); ++i)
    {
      size_t len = 0;
      Node *cur = _table[i];
      while(cur != nullptr)
      {
        ++len;
        cur = cur->_next;
      }
      if(len > max_len)
        max_len = len;
    }
    return max_len;
  }
};
